import java.util.Arrays;
import java.util.Map;

public class Solution {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        coinChange(coins, amount);
    }

    public static int coinChange(int[] coins, int amount) {
        //就是完全背包
        //dp[i] 是个数，i 是背包总容量
        int[] dp = new int[amount + 1];

        //因为是最少，且有可能没有的情况，返回-1
        //初始化为一个较大值，因为要往里面放入最小值
        //但是 dp[0] 放入0，组合肯定也就是0
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        //之后就是使用递推公式来完成了
        //这里我们先遍历物品
        //之后便利背包
        for (int i = 0; i < coins.length; i++) {
            //记住从前向后遍历
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }

        for (int i = 0; i < dp.length; i++) {
            System.out.print(dp[i] + " ");
        }

        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }

    public static int coinChange2(int[] coins, int amount) {
        int length = coins.length;
        Arrays.sort(coins);

        // 前i个元素
        int[][] dp = new int[length + 1][amount + 1];
        Arrays.fill(dp[0], Integer.MAX_VALUE / 2);
        dp[0][0] = 0;
        for (int i = 1; i <= length; i++) {
            for (int j = 0; j <= amount; j++) {
                dp[i][j] = dp[i - 1][j];
                for (int k = 0; k * coins[i - 1] <= j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - k * coins[i - 1]] + k);
                }
            }
        }

        for (int[] x : dp) {
            for (int y : x) {
                System.out.print(y + " ");
            }
            System.out.println();
        }

        int ans = dp[length][amount];

        return ans < Integer.MAX_VALUE / 2 ? ans : -1;
    }

    public static int coinChange1(int[] coins, int amount) {
        //就是完全背包
        //dp[i] 是个数，i 是背包总容量
        int[][] dp = new int[coins.length + 1][amount + 1];

        //初始化
        for (int i = 0; i <= coins.length; i++) {
            for (int j = 0; j <= amount; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                }
            }
        }
        //之后就是递推公式
        for (int i = 1; i <= coins.length; i++) {
            //先遍历物品
            for (int j = 1; j <= amount; j++) {
                //后便利背包
                //从前向后便利
                if (j >= coins[i]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - coins[i]] + 1);
                }
            }
        }

        for (int[] x : dp) {
            for (int y : x) {
                System.out.print(y + " ");
            }
            System.out.println();
        }

        return dp[coins.length][amount];
    }
}
